﻿// Sliding Window POJ - 2823.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//https://vjudge.csgrandeur.cn/problem/POJ-2823
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <deque>
#include <stdio.h>

using namespace std;


/*
给你一个大小为 n≤106 的数组。有一个大小为 k 的滑动窗口正在从数组的最左边向最右边移动。
你只能看到窗口中的 k 个数字。每次滑动窗口向右移动一个位置。
下面是一个示例：
数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
 1 [3 -1 -3] 5 3 6 7 -3 3
 1 3 [-1 -3 5] 3 6 7 -3 5
 1 3 -1 [-3 5 3] 6 7 -3 5
 1 3 -1 -3 [5 3 6] 7 3 6
 1 3 -1 -3 5 [3 6 7] 3 7
您的任务是确定滑动窗口中每个位置的最大值和最小值。

输入
输入由两行组成。第一行包含两个整数 n 和 k，分别是数组和滑动窗口的长度。第二行有 n 个整数。
输出
输出有两行。第一行从左到右分别给出窗口中每个位置的最小值。第二行给出最大值。

8 3
1 3 -1 -3 5 3 6 7

-1 -3 -3 -3 3 3
3 3 5 5 6 7


*/


const int N = 1000010;
int arr[N];
int n, k;


void solve() {
	deque<int> q;

	for (int i = 1; i <= n; i++) {
		while (!q.empty() && i - q.front() >= k) q.pop_front();
		while (!q.empty() && arr[i] <= arr[q.back()]) q.pop_back();
		q.push_back(i);
		if (i >= k) {
			cout << arr[q.front()] <<" ";
		}
	}
	cout << endl;

	q.clear();

	for (int i = 1; i <= n ; i++) {
		while (!q.empty() && i - q.front() >= k) q.pop_front();
		while (!q.empty() && arr[i]  >=  arr[q.back()]) q.pop_back();
		q.push_back(i);
		if (i >= k) {
			cout << arr[q.front()] << " ";
		}
	}
	cout << endl;
}


int main()
{
	scanf("%d%d",&n,&k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}

	solve();

	return 0;
}

 